Search results for "Hamming distance"
showing 6 items of 6 documents
"Indexing structures for approximate string matching
2003
In this paper we give the first, to our knowledge, structures and corresponding algorithms for approximate indexing, by considering the Hamming distance, having the following properties. i) Their size is linear times a polylog of the size of the text on average. ii) For each pattern x, the time spent by our algorithms for finding the list occ(x) of all occurrences of a pattern x in the text, up to a certain distance, is proportional on average to |x| + |occ(x)|, under an additional but realistic hypothesis.
On the Low-Dimensional Steiner Minimum Tree Problem in Hamming Metric
2011
It is known that the d-dimensional Steiner Minimum Tree Problem in Hamming metric is NP-complete if d is considered to be a part of the input. On the other hand, it was an open question whether the problem is also NP-complete in fixed dimensions. In this paper we answer this question by showing that the problem is NP-complete for any dimension strictly greater than 2. We also show that the Steiner ratio is 2 - 2/d for d ≥ 2. Using this result, we tailor the analysis of the so-called k-LCA approximation algorithm and show improved approximation guarantees for the special cases d = 3 and d = 4.
NP-completeness of the hamming salesman problem
1985
It is shown that the traveling salesman problem, where cities are bit strings with Hamming distances, is NP-complete.
Split decomposition A technique to analyze viral evolution
1993
A clustering technique allowing a restricted amount of overlapping and based on an abstract theory of coherent decompositions of finite metrics is used to analyze the evolution of foot-and-mouth disease viruses. The emerging picture is compatible with the existence of viral populations with a quasispecies structure and illustrates various forms of evolution of this virus family. In addition, it allows the correlation of these forms with geographic occurrence.
Selección de personal basada en métodos difusos
2011
[ES] Las decisiones de los directivos en cuanto a la selección de personal determinan en gran medida el éxito de la empresa. Una elección adecuada de los empleados proporciona una ventaja comparativa. Proponemos un método borroso para la selección de personal basado en la gestión de competencias y la comparación con la valoración que la empresa considera más adecuada para cada trabajo (el candidato ideal). Nuestro método utiliza la distancia de Hamming y el Matching Level Index. Los algoritmos, implementados con el software Sta¿Designer, nos permite establecer un ranking de candidatos, incluso cuando las competencias del candidato ideal han sido evaluadas tan solo en parte. Nuestro enfoque …
Variances as order parameter and complexity measure for random Boolean networks
2005
Several order parameters have been considered to predict and characterize the transition between ordered and disordered phases in random Boolean networks, such as the Hamming distance between replicas or the stable core, which have been successfully used. In this work, we propose a natural and clear new order parameter: the temporal variance. We compute its value analytically and compare it with the results of numerical experiments. Finally, we propose a complexity measure based on the compromise between temporal and spatial variances. This new order parameter and its related complexity measure can be easily applied to other complex systems.